spreading activation

Spreading activation is a way of reasoning over large networks or graphs. There are many variants, but in general they begin with some set of initial nodes of interst which are given an 'activation'. The nodes then pass on some or all of this activation to neighbouring nodes, and the process repeated so that the level of activation perculates outwards from the seed nodes throughout the graph. Typically thise nodes closer to the initial nodes end up with more actvation than those more distant and those that are connected to mutiple initial nodes get more highly activated.

Some spreading activation algorithms are conservative in that the total amount of actvation remains unchanged by the algorithm, any activation passed on from a node to others must come from its own stock. Others may be non-conservative meaning that the total amount of activation might increase or decrease over time.

In some variants, the seed nodes are constantly given fresh activation so that the effect is like a source of water or energy gradually spreading out. Also variants differ as to whether they stop after a fixed number of spreading cycles, or iterate until the system reaches a steady state. If there is no constant refilling the steady state is often related more to the graph structure than the inital seed activation.

In some applications, it is this graph structure that is wanted. An important example is the Google PageRank algorithm which can be viewed as a spreading activation over web pages and links. The simplest version of PageRank begins with a uniform initial activation and the spreading means that pages whuch are referenced from many other pages gradually aquire more activation, which is used as a measure of their importance and hence used to order search results.

In other applications, the initial activation is important. For example, in natural language processing, we might use recent references to entities to giving them initial activation and then use spreading activation over a semantic network to judge the relative likelhood of an {{ambiguous utterance}].